/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/coin-path
   @Language: C++
   @Datetime: 19-04-02 14:54
   */

class Solution {
public:
	/**
	 * @param A: a list of integer
	 * @param B: an integer
	 * @return: return a list of integer
	 * Tip:
	 * dp[i]: min cost from i to end
	 */
	vector<int> cheapestJump(vector<int> &A, int B) {
		// write your code here
		if(A.size()<1 || A.back()==-1 || B==0) return {};
		int n=A.size();
		vector<int> res, pos(n,-1), dp(n,INT_MAX);
		dp[n-1]=A[n-1];
		for(int i=n-1; i--;){
			if (A[i]==-1) continue;
			for(int j=i+1; j<min(i+B+1,n); ++j){
				if(dp[j]==INT_MAX) continue;
				if(dp[j]+A[i]<dp[i]){
					dp[i]=dp[j]+A[i];
					pos[i]=j;
				}
			}
		}
		if (dp[0]==INT_MAX) return {};
		for(int i=0; i!=-1; i=pos[i])
			res.push_back(i+1);
		return res;
	}
};
